class Node(object):
    """
    TriedTree节点
    """

    def __init__(self, name):
        """
        前缀树节点
        :param name: 节点名，除了根节点是root 其他都是字符
        """
        self.name = name
        self.children = {}
        self.is_word = False
        self.tag = ""


class TriedTree(object):
    """
    TriedTree分词器
    """

    def __init__(self):

        self.root = Node("root")

    def insert(self, word, tag=""):
        """
        插入单词
        :param tag:
        :param word:单词
        :return:
        """

        if word == "":
            return
        word = list(word)

        def do_insert(i, node):
            """
            递归插入单词
            :param i: 位置索引
            :param node:字母节点
            :return:
            """
            if i == len(word):
                node.is_word = True
                node.tag = tag
                return
            sub_node = node.children.get(word[i])
            if sub_node is None:
                sub_node = Node(word[i])
                node.children[word[i]] = sub_node
            do_insert(i + 1, sub_node)

        index = 0
        first_node = self.root.children.get(word[index])
        if first_node is None:
            first_node = Node(word[index])
            self.root.children[word[index]] = first_node
        do_insert(index + 1, first_node)

    def segment_word(self, sentence):
        """
        检测关键词，分词并且打标
        :param sentence:
        :return:
        """
        index = 0
        result = []

        if sentence == "":
            return result
        sentence = list(sentence)

        def deep_first_search(i, node):
            """
            深度优先搜索目标节点返回下标和节点标签
            :param i:
            :param node:
            :return:
            """
            # if node.children is None:
            #     return i
            if i == len(sentence) and node.is_word:
                return i, True, node.tag
            if i == len(sentence) and not node.is_word:
                return i, False, ""
            sub_node = node.children.get(sentence[i])

            if sub_node is None and node.is_word:
                return i, True, node.tag
            if sub_node is None and not node.is_word:
                return i, False, ""

            return deep_first_search(i + 1, sub_node)

        while index < len(sentence):

            first_node = self.root.children.get(sentence[index])
            begin = index
            index += 1
            if first_node is None:
                continue

            end, success, tag = deep_first_search(index, first_node)
            index = end
            if not success:
                continue

            result.append({"word": "".join(sentence[begin:end]), "tagger": tag, "begin": begin, "end": end})

        return result